「比赛总结」 正睿 国庆

📅 Last Updated: 2020-11-18
📊 Word Count: 118
⏱️ Estimated Reading Time: 1 minutes
📄 PDF 📝 Source

link

给出一个长度为 nn 的 01 串 ss 和整数 kk ，求一个 ss 最长的子串 tt 使得 tt 中 0 的个数是 1 的个数的 kk 倍，输出最长的 tt 的长度。

设$ S_0[i]$ 表示 S[1..i]S[1..i]中 0的数量。 S1[i]S_1[i] 表示 S[1..i]S[1..i]中 1的数量。 字串 S[L,R]S[L, R] 满足条件当且仅当 S0[R]−S0[L−1]=(S1[R]−S1[L−1])×kS_0[R] - S_0[L - 1] = (S_1[R] - S_1[L - 1]) \times k。 即：S0[R]−S1[R]×k=S0[L−1]−S1[L−1]×kS_0[R] - S_1[R] \times k = S_0[L - 1] - S_1[L - 1] \times k。

#define i64 long long 
const int _ = 1e6 + 100;
int n, k;
char S[_];
int S0[_], S1[_];
map<long long, int >M;
int main(){ 
    ios::sync_with_stdio(false);
    cin >> n >> k >> (S + 1); 
    for(int i = 1; i <= n; i++) S0[i] = S0[i - 1] + (S[i] == '0'), S1[i] = S1[i - 1] + (S[i] == '1');
    int ans = 0;  
    M[0] = 0;
    for(int i = 1; i <= n; i++){
        i64 now = S0[i] -0ll- k *1ll* S1[i];
        if(M.count(now)) ans = max(ans, i - M[now]);  else M[now] = i;
    }
    printf("%d\n", ans); cerr << "std's ans = " << ans << endl;
    return 0;
}

有两个长度为 nn 的排列 A,BA,B ，你每次可以进行三种操作： - 删除 AA 的第一个元素 aa - 删除 BB 的第一个元素 bb - 删除 AA 的第一个元素 aa 和 BB 的第一个元素 bb ，要求 a≠ba\neq b 求把 A,BA,B 都删光需要的最少操作次数。

n≤106n \le 10^6

当数列 A,BA, B 的首项相同的时候，直接贪心的选择操作 3 。需要决策当 A,BA, B 首项相同的时候选择删除那边的，然后又可以一直删，直到首项再次相同的时候 再决策，直接DP可能被卡住的地方即可。

设数字 xx 在 AA 中的位置是 ii，在 BB 中的位置是 jj，记 数字 xx 的位置为二元组 (i,j)(i, j)。由于 A,BA , B 是两个排列，对于数字 xx ，其位置一定是唯一的 (i,j)(i, j)。 设 dp⁡[i]\operatorname{dp}[i] 为 (设 AiA_i 的位置为 (i,j)(i, j) ) ，删光 A[i..n]A[i..n] 和 B[j..n]B[j..n] 的代价。

对于数值 xx 的位置 (i,j)(i, j) 设 $= i - j 。由于排列的性质，。由于排列的性质，dp[i]、、A_i$ 的位置 (i,j)(i, j)这些是一一对应的。设 Δ(x)\Delta(x) 为 dp[x]dp[x] 对应的 Δ\Delta。

转移就是

dp[i]=1+min⁡Δ(x)=Δ(i)−1,Δ(y)=Δ(i)+1{ dp[x]+dist⁡(i,x),  dp[y]+dist⁡(i,y) }dp[i] = 1 + \min_{\Delta(x) = \Delta(i) - 1, \Delta(y) = \Delta(i) + 1}\limits{\{\ dp[x] + \operatorname{dist}(i, x),\ \ dp[y] + \operatorname{dist}(i, y)}\ \}。

从后往前 dpdp 记录以下 Δ\Delta 即可。 为了方便，其中 Last⁡\operatorname{Last} 为 Δ()\Delta() 的反函数。

int n, A[_], B[_], POOL[(_ << 1) + 100], PosInB[_], *Last = &POOL[_ + 10];
int dp[_];
int main(){
    rep(i, 1, n = read()) Read(A[i]); rep(i, 1, n) Read(B[i]), PosInB[B[i]] = i;
    clear(dp, 0x3f); clear(POOL, -1);
    per(i, 1, n) {
        int det = i - PosInB[A[i]];
        if(Last[det + 1] != -1) to_min(dp[i], dp[Last[det + 1]] + 1 + (Last[det + 1] - (i + 1)));
        else to_min(dp[i], 1 + max(n - (i + 1) + 1, n - (PosInB[A[i]]) + 1 ));
        if(Last[det - 1] != -1) to_min(dp[i], dp[Last[det - 1]] + 1 + (Last[det - 1] - (i)));
        else to_min(dp[i], 1 + max(n - (i) + 1, n - (PosInB[A[i]] + 1) + 1));
        Last[det] = i;
    }
    int ans = 0;
    if(Last[0] == -1) ans = n; else ans = dp[Last[0]] + Last[0] - 1;
    printf("%d", ans);
    return 0;
}

对于长度为 nn 的置换 A,BA,B ，求是否存在正整数 kk 使得 Ak=BA^k=B

定义置换的乘法为 C=(A⋅B),Ci=ABiC = (A \cdot B), C_i=A_{B_i}

定义 A1=A,An=An−1⋅A(n>1)A^1=A,A^n=A^{n-1} \cdot A(n > 1)

如果存在 k 输出 Yes 否则输出 No 。

n≤106n \le 10^6

可以转化为对线性同于方程判断是否有解的问题。

这里的线性同于方程组的模数 ≤106\le 10^6 且不互质，LCMLCM 很大 无法 exCRTexCRT 合并。

O(nlog⁡n)O(n \operatorname{log} n)： 从 1 n1 ~ n 枚举 ii 尝试求出 xmod⁡ix \operatorname{mod} i 的数值，易知 这个值可以从 xmod⁡ki˙x \operatorname{mod} k \dot i 的值得到，检查方程组中所有的方程，看看是否冲突即可。根据调和级数，这样做的时间复杂度为 O(nlog⁡n)O(n \operatorname{log} n)。

#define i64 long long 
#define walk(now, ex) for(int i = head[now], ex; ex = edge[i].node, i; i = edge[i].nxt)
bool vis[_];
vector<int> G[_];
int D[_], SZ[_], BL[_];
int Dis[_], MD[_];
int cnt = 0;
void clear(){
    memset(head, 0, sizeof(head)); tot = 0;
    memset(vis, false, sizeof(vis));
    for(int i = 1; i <= cnt; i++) G[i].clear(); cnt = 0;
}
void dfs(int now, int target){
    G[target].push_back(now);  vis[now] = 1;
    walk(now, ex) { if(vis[ex]) continue; dfs(ex, target); }
}
bool CMP(const pair<int, int > & A, const pair<int, int > & B) { return A.fi < B.fi; }
int pos[_];
bool PdExist(int *Md, int *a, int n) {
    static vector< pair<int, int > > M, M0; M.clear(); M0.clear();
    for(int i = 1; i <= n; i++) M.push_back(make_pair(Md[i], a[i]));
    sort(M.begin(), M.end(), CMP);
    for(int i = 0; i < M.size(); i++) {
        int L = i, R = i;
        while(R + 1 < M.size() && M[L].fi == M[R + 1].fi) R++;
        for(int j = L; j <= R; j++) if(M[j].se != M[L].se) return false;
        M0.push_back(M[L]);
        i = R;
    }
    memset(pos, -1, sizeof(pos));
    int MAX = 0; for(int i = 0; i < M0.size(); i++) MAX = max(MAX, M0[i].fi), pos[M0[i].fi] = i;
    for(int i = 1; i <= MAX; i++){
        int tmp = -1;
        for(int j = i; j <= MAX; j += i) if(pos[j] != -1) { if(tmp == -1) tmp = M0[pos[j]].se % i; else if(tmp != M0[pos[j]].se % i) return false; }
    }
    return true;
}

void doit(){
    clear();
    for(int i = 1; i <= n; i++) add(A[i], i);
    for(int i = 1; i <= n; i++) if(!vis[i]) dfs(i, ++cnt);
    for(int i = 1; i <= cnt; i++) {
        for(int j = 0; j < G[i].size(); j++){
            D[G[i][j]] = j;
            SZ[G[i][j]] = G[i].size();
            BL[G[i][j]] = i;    
        }
    }
    for(int i = 1; i <= n; i++) if(BL[A[i]] != BL[B[i]]) { return (void)puts("No");}
    for(int i = 1; i <= n; i++) Dis[i] = ( D[B[i]] - D[A[i]] + SZ[A[i]] ) % SZ[A[i]];
    
    for(int i = 1; i <= n; i++) MD[i] = SZ[A[i]];
    int r = PdExist(MD, Dis, n);
    return (void)puts(r ? "Yes" : "No"); 
}

int main(){
    while(scanf("%d", &n) == 1){
        for(int i = 1; i <= n; i++) Read(A[i]);
        for(int i = 1; i <= n; i++) Read(B[i]);
        doit();
    }
    return 0;
}

📚 Version History

Source Code Change History
v1
🔗 Source Hash: 13978c5cc684e8804494290eab88099f9899e9618a11002427b5376b8a50f24c
Build Logs 
Build Log - Filtered
================================================

📋 Information:
• Path information has been filtered for privacy protection
• File names are preserved for debugging purposes  
• All build status and error messages are kept intact

🔍 Filter Rules:
• /absolute/path/file.ext → .../file.ext
• /home/username → .../[user]
• /tmp/files → .../[temp]
• /usr/share/packages → .../[system]

================================================

html log:
CMD: ['pandoc', '-s', 'cache/oi-blog_「比赛总结」 正睿 国庆.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache/oi-blog_「比赛总结」 正睿 国庆.md.html', '--metadata', '--verbose', '--highlight-style=tango']
STDOUT: 
STDERR: WARNING: pandoc-crossref was compiled with pandoc 3.6.2 but is being run through 3.6.4. This is not supported. Strange things may (and likely will) happen silently.

====================================================================================================
pdf log:
CMD: ['pandoc', '-s', 'cache.../b5c286cbd1.pdf.md', '-o', 'cache/b5c286cbd1.pdf', '-H', 'static/pandoc.header.tex', '--pdf-engine=xelatex', '--verbose']
STDOUT: 
STDERR: [INFO] Loaded static.../pandoc.header.tex from static.../pandoc.header.tex
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] [makePDF] Temp dir:
  .../[temp]
[INFO] [makePDF] Command line:
  xelatex "-halt-on-error" "-interaction" "nonstopmode" "-output-directory" ".../[temp] ".../[temp]
[INFO] [makePDF] Relevant environment variables:
  ("TEXINPUTS",".../[temp]
  ("TEXMFOUTPUT",".../[temp]
  ("SHELL","/bin/bash")
  ("PWD",".../[user]/projects/blog")
  ("HOME",".../[user]
  ("LANG","zh_CN.UTF-8")
  ("PATH",".../[user]/.local/bin:.../[user]/.cargo/bin:.../[user]/miniconda3/envs/myblog/bin:.../[user]/miniconda3/condabin:.../[temp]
[INFO] [makePDF] Source:
  % Options for packages loaded elsewhere
  \PassOptionsToPackage{unicode}{hyperref}
  \PassOptionsToPackage{hyphens}{url}
  \PassOptionsToPackage{space}{xeCJK}
  \documentclass[
  ]{article}
  \usepackage{xcolor}
  \usepackage[a4paper,margin=2cm]{geometry}
  \usepackage{amsmath,amssymb}
  \setcounter{secnumdepth}{-\maxdimen} % remove section numbering
  \usepackage{iftex}
  \ifPDFTeX
    \usepackage[T1]{fontenc}
    \usepackage[utf8]{inputenc}
    \usepackage{textcomp} % provide euro and other symbols
  \else % if luatex or xetex
    \usepackage{unicode-math} % this also loads fontspec
    \defaultfontfeatures{Scale=MatchLowercase}
    \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
  \fi
  \usepackage{lmodern}
  \ifPDFTeX\else
    % xetex/luatex font selection
    \setmainfont[]{Latin Modern Roman}
    \ifXeTeX
      \usepackage{xeCJK}
      \setCJKmainfont[]{AR PL UKai CN}
    \fi
    \ifLuaTeX
      \usepackage[]{luatexja-fontspec}
      \setmainjfont[]{AR PL UKai CN}
    \fi
  \fi
  % Use upquote if available, for straight quotes in verbatim environments
  \IfFileExists{upquote.sty}{\usepackage{upquote}}{}
  \IfFileExists{microtype.sty}{% use microtype if available
    \usepackage[]{microtype}
    \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
  }{}
  \usepackage{setspace}
  \makeatletter
  \@ifundefined{KOMAClassName}{% if non-KOMA class
    \IfFileExists{parskip.sty}{%
      \usepackage{parskip}
    }{% else
      \setlength{\parindent}{0pt}
      \setlength{\parskip}{6pt plus 2pt minus 1pt}}
  }{% if KOMA class
    \KOMAoptions{parskip=half}}
  \makeatother
  \usepackage{color}
  \usepackage{fancyvrb}
  \newcommand{\VerbBar}{|}
  \newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
  \DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
  % Add ',fontsize=\small' for more characters per line
  \newenvironment{Shaded}{}{}
  \newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
  \newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
  \newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\BuiltInTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{#1}}
  \newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
  \newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
  \newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
  \newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
  \newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
  \newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
  \newcommand{\ExtensionTok}[1]{#1}
  \newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
  \newcommand{\ImportTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{\textbf{#1}}}
  \newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
  \newcommand{\NormalTok}[1]{#1}
  \newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
  \newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
  \newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
  \newcommand{\RegionMarkerTok}[1]{#1}
  \newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
  \newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
  \newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \setlength{\emergencystretch}{3em} % prevent overfull lines
  \providecommand{\tightlist}{%
    \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
  % \usepackage{xeCJK}
  % \setCJKmainfont{AR PL UKai CN}
  % \usepackage{unicode-math}
  
  \setmathfont{Latin Modern Math}
  \usepackage{bookmark}
  \IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
  \urlstyle{same}
  \hypersetup{
    pdftitle={「比赛总结」 正睿 国庆},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{「比赛总结」 正睿 国庆}
  \author{Jiayi Su (ShuYuMo)}
  \date{2020-11-18 11:41:50}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  \href{http://zhengruioi.com/contest/766/problem/394}{link}
  
  给出一个长度为 \(n\) 的 \texttt{01} 串 \(s\) 和整数 \(k\) ，求一个 \(s\)
  最长的子串 \(t\) 使得 \(t\) 中 \texttt{0} 的个数是 \texttt{1} 的个数的
  \(k\) 倍，输出最长的 \(t\) 的长度。
  
  设\$ S\_0{[}i{]}\$ 表示 \(S[1..i]\)中 \texttt{0}的数量。 \(S_1[i]\) 表示
  \(S[1..i]\)中 \texttt{1}的数量。 字串 \(S[L, R]\) 满足条件当且仅当
  \(S_0[R] - S_0[L - 1] = (S_1[R] - S_1[L - 1]) \times k\)。
  即：\(S_0[R] - S_1[R] \times k = S_0[L - 1] - S_1[L - 1] \times k\)。
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \PreprocessorTok{\#define i64 }\DataTypeTok{long}\PreprocessorTok{ }\DataTypeTok{long}\PreprocessorTok{ }
  \AttributeTok{const} \DataTypeTok{int}\NormalTok{ \_ }\OperatorTok{=} \FloatTok{1e6} \OperatorTok{+} \DecValTok{100}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ n}\OperatorTok{,}\NormalTok{ k}\OperatorTok{;}
  \DataTypeTok{char}\NormalTok{ S}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ S0}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ S1}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \NormalTok{map}\OperatorTok{\textless{}}\DataTypeTok{long} \DataTypeTok{long}\OperatorTok{,} \DataTypeTok{int} \OperatorTok{\textgreater{}}\NormalTok{M}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ main}\OperatorTok{()\{} 
  \NormalTok{    ios}\OperatorTok{::}\NormalTok{sync\_with\_stdio}\OperatorTok{(}\KeywordTok{false}\OperatorTok{);}
  \NormalTok{    cin }\OperatorTok{\textgreater{}\textgreater{}}\NormalTok{ n }\OperatorTok{\textgreater{}\textgreater{}}\NormalTok{ k }\OperatorTok{\textgreater{}\textgreater{}} \OperatorTok{(}\NormalTok{S }\OperatorTok{+} \DecValTok{1}\OperatorTok{);} 
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ S0}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ S0}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{]} \OperatorTok{+} \OperatorTok{(}\NormalTok{S}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{==} \CharTok{\textquotesingle{}0\textquotesingle{}}\OperatorTok{),}\NormalTok{ S1}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ S1}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{]} \OperatorTok{+} \OperatorTok{(}\NormalTok{S}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{==} \CharTok{\textquotesingle{}1\textquotesingle{}}\OperatorTok{);}
      \DataTypeTok{int}\NormalTok{ ans }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}  
  \NormalTok{    M}\OperatorTok{[}\DecValTok{0}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
  \NormalTok{        i64 now }\OperatorTok{=}\NormalTok{ S0}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{{-}}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{{-}}\NormalTok{ k }\OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ S1}\OperatorTok{[}\NormalTok{i}\OperatorTok{];}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{M}\OperatorTok{.}\NormalTok{count}\OperatorTok{(}\NormalTok{now}\OperatorTok{))}\NormalTok{ ans }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{ans}\OperatorTok{,}\NormalTok{ i }\OperatorTok{{-}}\NormalTok{ M}\OperatorTok{[}\NormalTok{now}\OperatorTok{]);}  \ControlFlowTok{else}\NormalTok{ M}\OperatorTok{[}\NormalTok{now}\OperatorTok{]} \OperatorTok{=}\NormalTok{ i}\OperatorTok{;}
      \OperatorTok{\}}
  \NormalTok{    printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%d\textbackslash{}n}\StringTok{"}\OperatorTok{,}\NormalTok{ ans}\OperatorTok{);}\NormalTok{ cerr }\OperatorTok{\textless{}\textless{}} \StringTok{"std\textquotesingle{}s ans = "} \OperatorTok{\textless{}\textless{}}\NormalTok{ ans }\OperatorTok{\textless{}\textless{}}\NormalTok{ endl}\OperatorTok{;}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  有两个长度为 \(n\) 的排列 \(A,B\) ，你每次可以进行三种操作： - 删除
  \(A\) 的第一个元素 \(a\) - 删除 \(B\) 的第一个元素 \(b\) - 删除 \(A\)
  的第一个元素 \(a\) 和 \(B\) 的第一个元素 \(b\) ，要求 \(a\neq b\) 求把
  \(A,B\) 都删光需要的最少操作次数。
  
  \(n \le 10^6\)
  
  当数列 \(A, B\) 的首项相同的时候，直接贪心的选择操作 3 。需要决策当
  \(A, B\)
  首项相同的时候选择删除那边的，然后又可以一直删，直到首项再次相同的时候
  再决策，直接DP可能被\textbf{卡住}的地方即可。
  
  设数字 \(x\) 在 \(A\) 中的位置是 \(i\)，在 \(B\) 中的位置是 \(j\)，记
  数字 \(x\) 的位置为二元组 \((i, j)\)。由于 \(A , B\)
  是两个排列，对于数字 \(x\) ，其位置一定是唯一的 \((i, j)\)。 设
  \(\operatorname{dp}[i]\) 为 (设 \(A_i\) 的位置为 \((i, j)\) ) ，删光
  \(A[i..n]\) 和 \(B[j..n]\) 的代价。
  
  对于数值 \(x\) 的位置 \((i, j)\) 设 \$\Delta = i - j
  \(。由于排列的性质，\)dp{[}i{]}\(、\)A\_i\$ 的位置
  \((i, j)\)这些是一一对应的。设 \(\Delta(x)\) 为 \(dp[x]\) 对应的
  \(\Delta\)。
  
  转移就是
  
  \(dp[i] = 1 + \min_{\Delta(x) = \Delta(i) - 1, \Delta(y) = \Delta(i) + 1}\limits{\{\ dp[x] + \operatorname{dist}(i, x),\ \ dp[y] + \operatorname{dist}(i, y)}\ \}\)。
  
  从后往前 \(dp\) 记录以下 \(\Delta\) 即可。 为了方便，其中
  \(\operatorname{Last}\) 为 \(\Delta()\) 的反函数。
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \DataTypeTok{int}\NormalTok{ n}\OperatorTok{,}\NormalTok{ A}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ B}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ POOL}\OperatorTok{[(}\NormalTok{\_ }\OperatorTok{\textless{}\textless{}} \DecValTok{1}\OperatorTok{)} \OperatorTok{+} \DecValTok{100}\OperatorTok{],}\NormalTok{ PosInB}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],} \OperatorTok{*}\NormalTok{Last }\OperatorTok{=} \OperatorTok{\&}\NormalTok{POOL}\OperatorTok{[}\NormalTok{\_ }\OperatorTok{+} \DecValTok{10}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ dp}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ main}\OperatorTok{()\{}
  \NormalTok{    rep}\OperatorTok{(}\NormalTok{i}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ n }\OperatorTok{=}\NormalTok{ read}\OperatorTok{())}\NormalTok{ Read}\OperatorTok{(}\NormalTok{A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]);}\NormalTok{ rep}\OperatorTok{(}\NormalTok{i}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ n}\OperatorTok{)}\NormalTok{ Read}\OperatorTok{(}\NormalTok{B}\OperatorTok{[}\NormalTok{i}\OperatorTok{]),}\NormalTok{ PosInB}\OperatorTok{[}\NormalTok{B}\OperatorTok{[}\NormalTok{i}\OperatorTok{]]} \OperatorTok{=}\NormalTok{ i}\OperatorTok{;}
  \NormalTok{    clear}\OperatorTok{(}\NormalTok{dp}\OperatorTok{,} \BaseNTok{0x3f}\OperatorTok{);}\NormalTok{ clear}\OperatorTok{(}\NormalTok{POOL}\OperatorTok{,} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{);}
  \NormalTok{    per}\OperatorTok{(}\NormalTok{i}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ n}\OperatorTok{)} \OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ det }\OperatorTok{=}\NormalTok{ i }\OperatorTok{{-}}\NormalTok{ PosInB}\OperatorTok{[}\NormalTok{A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]];}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{Last}\OperatorTok{[}\NormalTok{det }\OperatorTok{+} \DecValTok{1}\OperatorTok{]} \OperatorTok{!=} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{)}\NormalTok{ to\_min}\OperatorTok{(}\NormalTok{dp}\OperatorTok{[}\NormalTok{i}\OperatorTok{],}\NormalTok{ dp}\OperatorTok{[}\NormalTok{Last}\OperatorTok{[}\NormalTok{det }\OperatorTok{+} \DecValTok{1}\OperatorTok{]]} \OperatorTok{+} \DecValTok{1} \OperatorTok{+} \OperatorTok{(}\NormalTok{Last}\OperatorTok{[}\NormalTok{det }\OperatorTok{+} \DecValTok{1}\OperatorTok{]} \OperatorTok{{-}} \OperatorTok{(}\NormalTok{i }\OperatorTok{+} \DecValTok{1}\OperatorTok{)));}
          \ControlFlowTok{else}\NormalTok{ to\_min}\OperatorTok{(}\NormalTok{dp}\OperatorTok{[}\NormalTok{i}\OperatorTok{],} \DecValTok{1} \OperatorTok{+}\NormalTok{ max}\OperatorTok{(}\NormalTok{n }\OperatorTok{{-}} \OperatorTok{(}\NormalTok{i }\OperatorTok{+} \DecValTok{1}\OperatorTok{)} \OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ n }\OperatorTok{{-}} \OperatorTok{(}\NormalTok{PosInB}\OperatorTok{[}\NormalTok{A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]])} \OperatorTok{+} \DecValTok{1} \OperatorTok{));}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{Last}\OperatorTok{[}\NormalTok{det }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{]} \OperatorTok{!=} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{)}\NormalTok{ to\_min}\OperatorTok{(}\NormalTok{dp}\OperatorTok{[}\NormalTok{i}\OperatorTok{],}\NormalTok{ dp}\OperatorTok{[}\NormalTok{Last}\OperatorTok{[}\NormalTok{det }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{]]} \OperatorTok{+} \DecValTok{1} \OperatorTok{+} \OperatorTok{(}\NormalTok{Last}\OperatorTok{[}\NormalTok{det }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{]} \OperatorTok{{-}} \OperatorTok{(}\NormalTok{i}\OperatorTok{)));}
          \ControlFlowTok{else}\NormalTok{ to\_min}\OperatorTok{(}\NormalTok{dp}\OperatorTok{[}\NormalTok{i}\OperatorTok{],} \DecValTok{1} \OperatorTok{+}\NormalTok{ max}\OperatorTok{(}\NormalTok{n }\OperatorTok{{-}} \OperatorTok{(}\NormalTok{i}\OperatorTok{)} \OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ n }\OperatorTok{{-}} \OperatorTok{(}\NormalTok{PosInB}\OperatorTok{[}\NormalTok{A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]]} \OperatorTok{+} \DecValTok{1}\OperatorTok{)} \OperatorTok{+} \DecValTok{1}\OperatorTok{));}
  \NormalTok{        Last}\OperatorTok{[}\NormalTok{det}\OperatorTok{]} \OperatorTok{=}\NormalTok{ i}\OperatorTok{;}
      \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ ans }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \ControlFlowTok{if}\OperatorTok{(}\NormalTok{Last}\OperatorTok{[}\DecValTok{0}\OperatorTok{]} \OperatorTok{==} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{)}\NormalTok{ ans }\OperatorTok{=}\NormalTok{ n}\OperatorTok{;} \ControlFlowTok{else}\NormalTok{ ans }\OperatorTok{=}\NormalTok{ dp}\OperatorTok{[}\NormalTok{Last}\OperatorTok{[}\DecValTok{0}\OperatorTok{]]} \OperatorTok{+}\NormalTok{ Last}\OperatorTok{[}\DecValTok{0}\OperatorTok{]} \OperatorTok{{-}} \DecValTok{1}\OperatorTok{;}
  \NormalTok{    printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%d}\StringTok{"}\OperatorTok{,}\NormalTok{ ans}\OperatorTok{);}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  对于长度为 \(n\) 的置换 \(A,B\) ，求是否存在正整数 \(k\) 使得 \(A^k=B\)
  
  定义置换的乘法为 \(C = (A \cdot B), C_i=A_{B_i}\)
  
  定义 \(A^1=A,A^n=A^{n-1} \cdot A(n > 1)\)
  
  如果存在 \texttt{k} 输出 \texttt{Yes} 否则输出 \texttt{No} 。
  
  \(n \le 10^6\)
  
  可以转化为对线性同于方程判断是否有解的问题。
  
  这里的线性同于方程组的模数 \(\le 10^6\) 且不互质，\(LCM\) 很大 无法
  \(exCRT\) 合并。
  
  \(O(n \operatorname{log} n)\)： 从 \(1 ~ n\) 枚举 \(i\) 尝试求出
  \(x \operatorname{mod} i\) 的数值，易知 这个值可以从
  \(x \operatorname{mod} k \dot i\)
  的值得到，检查方程组中所有的方程，看看是否冲突即可。根据调和级数，这样做的时间复杂度为
  \(O(n \operatorname{log} n)\)。
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \PreprocessorTok{\#define i64 }\DataTypeTok{long}\PreprocessorTok{ }\DataTypeTok{long}\PreprocessorTok{ }
  \PreprocessorTok{\#define walk}\OperatorTok{(}\NormalTok{now}\OperatorTok{,}\PreprocessorTok{ }\NormalTok{ex}\OperatorTok{)}\PreprocessorTok{ }\ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\PreprocessorTok{ }\NormalTok{i}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\NormalTok{head}\OperatorTok{[}\NormalTok{now}\OperatorTok{],}\PreprocessorTok{ }\NormalTok{ex}\OperatorTok{;}\PreprocessorTok{ }\NormalTok{ex}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\NormalTok{edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{,}\PreprocessorTok{ }\NormalTok{i}\OperatorTok{;}\PreprocessorTok{ }\NormalTok{i}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\NormalTok{edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{nxt}\OperatorTok{)}
  \DataTypeTok{bool}\NormalTok{ vis}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \NormalTok{vector}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{\textgreater{}}\NormalTok{ G}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ D}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ SZ}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ BL}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ Dis}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ MD}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ cnt }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \DataTypeTok{void}\NormalTok{ clear}\OperatorTok{()\{}
  \NormalTok{    memset}\OperatorTok{(}\NormalTok{head}\OperatorTok{,} \DecValTok{0}\OperatorTok{,} \KeywordTok{sizeof}\OperatorTok{(}\NormalTok{head}\OperatorTok{));}\NormalTok{ tot }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \NormalTok{    memset}\OperatorTok{(}\NormalTok{vis}\OperatorTok{,} \KeywordTok{false}\OperatorTok{,} \KeywordTok{sizeof}\OperatorTok{(}\NormalTok{vis}\OperatorTok{));}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ cnt}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ G}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{clear}\OperatorTok{();}\NormalTok{ cnt }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \DataTypeTok{void}\NormalTok{ dfs}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ now}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ target}\OperatorTok{)\{}
  \NormalTok{    G}\OperatorTok{[}\NormalTok{target}\OperatorTok{].}\NormalTok{push\_back}\OperatorTok{(}\NormalTok{now}\OperatorTok{);}\NormalTok{  vis}\OperatorTok{[}\NormalTok{now}\OperatorTok{]} \OperatorTok{=} \DecValTok{1}\OperatorTok{;}
  \NormalTok{    walk}\OperatorTok{(}\NormalTok{now}\OperatorTok{,}\NormalTok{ ex}\OperatorTok{)} \OperatorTok{\{} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{vis}\OperatorTok{[}\NormalTok{ex}\OperatorTok{])} \ControlFlowTok{continue}\OperatorTok{;}\NormalTok{ dfs}\OperatorTok{(}\NormalTok{ex}\OperatorTok{,}\NormalTok{ target}\OperatorTok{);} \OperatorTok{\}}
  \OperatorTok{\}}
  \DataTypeTok{bool}\NormalTok{ CMP}\OperatorTok{(}\AttributeTok{const}\NormalTok{ pair}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{,} \DataTypeTok{int} \OperatorTok{\textgreater{}} \OperatorTok{\&}\NormalTok{ A}\OperatorTok{,} \AttributeTok{const}\NormalTok{ pair}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{,} \DataTypeTok{int} \OperatorTok{\textgreater{}} \OperatorTok{\&}\NormalTok{ B}\OperatorTok{)} \OperatorTok{\{} \ControlFlowTok{return}\NormalTok{ A}\OperatorTok{.}\NormalTok{fi }\OperatorTok{\textless{}}\NormalTok{ B}\OperatorTok{.}\NormalTok{fi}\OperatorTok{;} \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ pos}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{bool}\NormalTok{ PdExist}\OperatorTok{(}\DataTypeTok{int} \OperatorTok{*}\NormalTok{Md}\OperatorTok{,} \DataTypeTok{int} \OperatorTok{*}\NormalTok{a}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ n}\OperatorTok{)} \OperatorTok{\{}
      \AttributeTok{static}\NormalTok{ vector}\OperatorTok{\textless{}}\NormalTok{ pair}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{,} \DataTypeTok{int} \OperatorTok{\textgreater{}} \OperatorTok{\textgreater{}}\NormalTok{ M}\OperatorTok{,}\NormalTok{ M0}\OperatorTok{;}\NormalTok{ M}\OperatorTok{.}\NormalTok{clear}\OperatorTok{();}\NormalTok{ M0}\OperatorTok{.}\NormalTok{clear}\OperatorTok{();}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ M}\OperatorTok{.}\NormalTok{push\_back}\OperatorTok{(}\NormalTok{make\_pair}\OperatorTok{(}\NormalTok{Md}\OperatorTok{[}\NormalTok{i}\OperatorTok{],}\NormalTok{ a}\OperatorTok{[}\NormalTok{i}\OperatorTok{]));}
  \NormalTok{    sort}\OperatorTok{(}\NormalTok{M}\OperatorTok{.}\NormalTok{begin}\OperatorTok{(),}\NormalTok{ M}\OperatorTok{.}\NormalTok{end}\OperatorTok{(),}\NormalTok{ CMP}\OperatorTok{);}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}}\NormalTok{ M}\OperatorTok{.}\NormalTok{size}\OperatorTok{();}\NormalTok{ i}\OperatorTok{++)} \OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ L }\OperatorTok{=}\NormalTok{ i}\OperatorTok{,}\NormalTok{ R }\OperatorTok{=}\NormalTok{ i}\OperatorTok{;}
          \ControlFlowTok{while}\OperatorTok{(}\NormalTok{R }\OperatorTok{+} \DecValTok{1} \OperatorTok{\textless{}}\NormalTok{ M}\OperatorTok{.}\NormalTok{size}\OperatorTok{()} \OperatorTok{\&\&}\NormalTok{ M}\OperatorTok{[}\NormalTok{L}\OperatorTok{].}\NormalTok{fi }\OperatorTok{==}\NormalTok{ M}\OperatorTok{[}\NormalTok{R }\OperatorTok{+} \DecValTok{1}\OperatorTok{].}\NormalTok{fi}\OperatorTok{)}\NormalTok{ R}\OperatorTok{++;}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ j }\OperatorTok{=}\NormalTok{ L}\OperatorTok{;}\NormalTok{ j }\OperatorTok{\textless{}=}\NormalTok{ R}\OperatorTok{;}\NormalTok{ j}\OperatorTok{++)} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{M}\OperatorTok{[}\NormalTok{j}\OperatorTok{].}\NormalTok{se }\OperatorTok{!=}\NormalTok{ M}\OperatorTok{[}\NormalTok{L}\OperatorTok{].}\NormalTok{se}\OperatorTok{)} \ControlFlowTok{return} \KeywordTok{false}\OperatorTok{;}
  \NormalTok{        M0}\OperatorTok{.}\NormalTok{push\_back}\OperatorTok{(}\NormalTok{M}\OperatorTok{[}\NormalTok{L}\OperatorTok{]);}
  \NormalTok{        i }\OperatorTok{=}\NormalTok{ R}\OperatorTok{;}
      \OperatorTok{\}}
  \NormalTok{    memset}\OperatorTok{(}\NormalTok{pos}\OperatorTok{,} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{,} \KeywordTok{sizeof}\OperatorTok{(}\NormalTok{pos}\OperatorTok{));}
      \DataTypeTok{int}\NormalTok{ MAX }\OperatorTok{=} \DecValTok{0}\OperatorTok{;} \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}}\NormalTok{ M0}\OperatorTok{.}\NormalTok{size}\OperatorTok{();}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ MAX }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{MAX}\OperatorTok{,}\NormalTok{ M0}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{fi}\OperatorTok{),}\NormalTok{ pos}\OperatorTok{[}\NormalTok{M0}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{fi}\OperatorTok{]} \OperatorTok{=}\NormalTok{ i}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ MAX}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
          \DataTypeTok{int}\NormalTok{ tmp }\OperatorTok{=} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{;}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ j }\OperatorTok{=}\NormalTok{ i}\OperatorTok{;}\NormalTok{ j }\OperatorTok{\textless{}=}\NormalTok{ MAX}\OperatorTok{;}\NormalTok{ j }\OperatorTok{+=}\NormalTok{ i}\OperatorTok{)} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{pos}\OperatorTok{[}\NormalTok{j}\OperatorTok{]} \OperatorTok{!=} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{)} \OperatorTok{\{} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{tmp }\OperatorTok{==} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{)}\NormalTok{ tmp }\OperatorTok{=}\NormalTok{ M0}\OperatorTok{[}\NormalTok{pos}\OperatorTok{[}\NormalTok{j}\OperatorTok{]].}\NormalTok{se }\OperatorTok{\%}\NormalTok{ i}\OperatorTok{;} \ControlFlowTok{else} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{tmp }\OperatorTok{!=}\NormalTok{ M0}\OperatorTok{[}\NormalTok{pos}\OperatorTok{[}\NormalTok{j}\OperatorTok{]].}\NormalTok{se }\OperatorTok{\%}\NormalTok{ i}\OperatorTok{)} \ControlFlowTok{return} \KeywordTok{false}\OperatorTok{;} \OperatorTok{\}}
      \OperatorTok{\}}
      \ControlFlowTok{return} \KeywordTok{true}\OperatorTok{;}
  \OperatorTok{\}}
  
  \DataTypeTok{void}\NormalTok{ doit}\OperatorTok{()\{}
  \NormalTok{    clear}\OperatorTok{();}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ add}\OperatorTok{(}\NormalTok{A}\OperatorTok{[}\NormalTok{i}\OperatorTok{],}\NormalTok{ i}\OperatorTok{);}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)} \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{vis}\OperatorTok{[}\NormalTok{i}\OperatorTok{])}\NormalTok{ dfs}\OperatorTok{(}\NormalTok{i}\OperatorTok{,} \OperatorTok{++}\NormalTok{cnt}\OperatorTok{);}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ cnt}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)} \OperatorTok{\{}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ j }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}\NormalTok{ j }\OperatorTok{\textless{}}\NormalTok{ G}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{size}\OperatorTok{();}\NormalTok{ j}\OperatorTok{++)\{}
  \NormalTok{            D}\OperatorTok{[}\NormalTok{G}\OperatorTok{[}\NormalTok{i}\OperatorTok{][}\NormalTok{j}\OperatorTok{]]} \OperatorTok{=}\NormalTok{ j}\OperatorTok{;}
  \NormalTok{            SZ}\OperatorTok{[}\NormalTok{G}\OperatorTok{[}\NormalTok{i}\OperatorTok{][}\NormalTok{j}\OperatorTok{]]} \OperatorTok{=}\NormalTok{ G}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{size}\OperatorTok{();}
  \NormalTok{            BL}\OperatorTok{[}\NormalTok{G}\OperatorTok{[}\NormalTok{i}\OperatorTok{][}\NormalTok{j}\OperatorTok{]]} \OperatorTok{=}\NormalTok{ i}\OperatorTok{;}    
          \OperatorTok{\}}
      \OperatorTok{\}}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{BL}\OperatorTok{[}\NormalTok{A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]]} \OperatorTok{!=}\NormalTok{ BL}\OperatorTok{[}\NormalTok{B}\OperatorTok{[}\NormalTok{i}\OperatorTok{]])} \OperatorTok{\{} \ControlFlowTok{return} \OperatorTok{(}\DataTypeTok{void}\OperatorTok{)}\NormalTok{puts}\OperatorTok{(}\StringTok{"No"}\OperatorTok{);\}}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ Dis}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=} \OperatorTok{(}\NormalTok{ D}\OperatorTok{[}\NormalTok{B}\OperatorTok{[}\NormalTok{i}\OperatorTok{]]} \OperatorTok{{-}}\NormalTok{ D}\OperatorTok{[}\NormalTok{A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]]} \OperatorTok{+}\NormalTok{ SZ}\OperatorTok{[}\NormalTok{A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]]} \OperatorTok{)} \OperatorTok{\%}\NormalTok{ SZ}\OperatorTok{[}\NormalTok{A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]];}
      
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ MD}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ SZ}\OperatorTok{[}\NormalTok{A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]];}
      \DataTypeTok{int}\NormalTok{ r }\OperatorTok{=}\NormalTok{ PdExist}\OperatorTok{(}\NormalTok{MD}\OperatorTok{,}\NormalTok{ Dis}\OperatorTok{,}\NormalTok{ n}\OperatorTok{);}
      \ControlFlowTok{return} \OperatorTok{(}\DataTypeTok{void}\OperatorTok{)}\NormalTok{puts}\OperatorTok{(}\NormalTok{r }\OperatorTok{?} \StringTok{"Yes"} \OperatorTok{:} \StringTok{"No"}\OperatorTok{);} 
  \OperatorTok{\}}
  
  \DataTypeTok{int}\NormalTok{ main}\OperatorTok{()\{}
      \ControlFlowTok{while}\OperatorTok{(}\NormalTok{scanf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%d}\StringTok{"}\OperatorTok{,} \OperatorTok{\&}\NormalTok{n}\OperatorTok{)} \OperatorTok{==} \DecValTok{1}\OperatorTok{)\{}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ Read}\OperatorTok{(}\NormalTok{A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]);}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ Read}\OperatorTok{(}\NormalTok{B}\OperatorTok{[}\NormalTok{i}\OperatorTok{]);}
  \NormalTok{        doit}\OperatorTok{();}
      \OperatorTok{\}}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  
  \end{document}
[INFO] [makePDF] LaTeX run number 1
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../fancyvrb.sty)
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty
  (.../infwarerr.sty)))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  No file input.aux.
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  
  Package hyperref Warning: Rerun to get /PageLabels entry.
  
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 159.
  
  Missing character: There is no 𝛥 (U+1D6E5) in font Latin Modern Roman 10 Regula
  r/OT:script=latn;language=dflt;mapping=tex-text;!
  Missing character: There is no 。 (U+3002) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no 由 (U+7531) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no 于 (U+4E8E) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no 排 (U+6392) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no 列 (U+5217) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no 的 (U+7684) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no 性 (U+6027) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no 质 (U+8D28) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no ， (U+FF0C) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no 、 (U+3001) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  [1] [2] [3] [4] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  Output written on .../input.pdf (4 pages).
  Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
  Package hyperref Warning: Rerun to get /PageLabels entry.
[INFO] [makePDF] LaTeX run number 2
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../fancyvrb.sty)
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty
  (.../infwarerr.sty)))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  (.../input.aux)
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 159.
  
  Missing character: There is no 𝛥 (U+1D6E5) in font Latin Modern Roman 10 Regula
  r/OT:script=latn;language=dflt;mapping=tex-text;!
  Missing character: There is no 。 (U+3002) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no 由 (U+7531) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no 于 (U+4E8E) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no 排 (U+6392) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no 列 (U+5217) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no 的 (U+7684) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no 性 (U+6027) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no 质 (U+8D28) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no ， (U+FF0C) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no 、 (U+3001) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  [1] [2] [3] [4] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  Output written on .../input.pdf (4 pages).
  Transcript written on .../input.log.
[WARNING] Missing character: There is no 𝛥 (U+1D6E5) (U+1D6E5) in font Latin Modern Roman 10 Regula
[WARNING] Missing character: There is no 。 (U+3002) (U+3002) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no 由 (U+7531) (U+7531) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no 于 (U+4E8E) (U+4E8E) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no 排 (U+6392) (U+6392) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no 列 (U+5217) (U+5217) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no 的 (U+7684) (U+7684) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no 性 (U+6027) (U+6027) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no 质 (U+8D28) (U+8D28) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no ， (U+FF0C) (U+FF0C) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no 、 (U+3001) (U+3001) in font LatinModernMath-Regular/OT:sc